use std::cell::{Ref, RefCell, RefMut};
use std::ops::Deref;
use std::rc::Rc;
use crate::Node;

// 双链表
#[derive(Clone)]
pub struct DNode<T> {
    elem: T,
    next: DLink<T>,
    prev: DLink<T>,
}

type DLink<T> = Option<Rc<RefCell<DNode<T>>>>;

#[derive(Clone)]
pub struct DList<T> {
    head: DLink<T>,
    tail: DLink<T>,
}


impl<T> DNode<T> {
    fn new(elem: T) -> Rc<RefCell<DNode<T>>> {
        Rc::new(RefCell::new(DNode {
            elem,
            next: DLink::None,
            prev: DLink::None,
        }))
    }
}

impl<T> DList<T> {
    pub fn new() -> DList<T> {
        DList {
            head: DLink::None,
            tail: DLink::None,
        }
    }


    // 从head add element
    pub fn push_front(&mut self, ele: T) {
        let mut node = DNode::new(ele);
        match self.head.take() {
            //head存在元素
            Some(head) => {
                head.borrow_mut().prev = Some(node.clone());
                node.borrow_mut().next = Some(head);
                self.head = Some(node);
            }
            // head 不存在元素
            None => {
                self.head = Some(node.clone());
                self.tail = Some(node);
            }
        }
    }


    //  从 head 取出 元素
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            // node 就是head
            // 取出 head 的下一个元素
            match node.borrow_mut().next.take() {
                Some(next) => {
                    //next 是head的next

                    //将next 的prev 指向None
                    next.borrow_mut().prev = None;
                    // list的 head 指向 next
                    self.head = Some(next);
                }

                //  head的next 不存在， 说明 list 就一个元素，  head 和tail 是指向一个元素 ,将 head 和tail 同时赋值为None
                None => {
                    self.head = None;
                    self.tail = None;
                }
            }

            // 将node 的next 指向None
            node.borrow_mut().next = None;
            Rc::try_unwrap(node).ok().unwrap().into_inner().elem
        })
    }


    //  从 head 取出 元素的值
    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |n| &n.elem)
        })
    }


    pub fn peek_front_mut(&self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |n| &mut n.elem)
        })
    }

    // 从后面 add element
    pub fn push_back(&mut self, ele: T) {
        let mut node = DNode::new(ele);
        match self.tail.take() {
            //tail存在元素
            Some(tail) => {
                tail.borrow_mut().next = Some(node.clone());
                node.borrow_mut().prev = Some(tail);
                self.tail = Some(node);
            }
            // tail 不存在元素
            None => {
                self.head = Some(node.clone());
                self.tail = Some(node);
            }
        }
    }


    //  从 后面 取出 元素
    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|node| {
            match node.borrow_mut().prev.take() {
                Some(prev) => {
                    prev.borrow_mut().next = None;
                    self.tail = Some(prev);
                }
                None => {
                    self.head = None;
                    self.tail = None;
                }
            }
            node.borrow_mut().prev = None;
            Rc::try_unwrap(node).ok().unwrap().into_inner().elem
        })
    }


    //  从 后面 取出 元素的值
    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |n| &n.elem)
        })
    }


    pub fn peek_back_mut(&self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |n| &mut n.elem)
        })
    }
}


pub struct IntoIter<T>(DList<T>);


impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.0.pop_front();
        next
    }
}


impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let next = self.0.pop_back();
        next
    }
}


impl<T> DList<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

#[cfg(test)]
mod test {
    use crate::d_link_list::DList;

    #[test]
    fn test_push_front() {
        let mut d_list = DList::new();
        d_list.push_front(11);
        d_list.push_front(22);
        d_list.push_front(33);
        d_list.push_front(44);

        println!("-----");
    }


    #[test]
    fn test_pop_front() {
        let mut d_list = DList::new();
        d_list.push_front(11);
        d_list.push_front(22);
        d_list.push_front(33);
        d_list.push_front(44);

        assert_eq!(d_list.pop_front(), Some(44));
        assert_eq!(d_list.pop_front(), Some(33));
        assert_eq!(d_list.pop_front(), Some(22));
        assert_eq!(d_list.pop_front(), Some(11));
        assert_eq!(d_list.pop_front(), None);
    }


    #[test]
    fn test_peek_front() {
        let mut d_list = DList::new();
        d_list.push_front(11);
        d_list.push_front(22);
        d_list.push_front(33);
        d_list.push_front(44);

        let binding = d_list.peek_front().unwrap();
        let head_ref = *binding;
        assert_eq!(head_ref, 44);
    }


    #[test]
    fn test_back() {
        let mut d_list = DList::new();
        d_list.push_back(11);
        d_list.push_back(22);
        d_list.push_back(33);
        d_list.push_back(44);


        let tail = *d_list.peek_back().unwrap();  //  只是取出值， node还在
        assert_eq!(tail, 44);

        let tail = d_list.pop_back();  //    取出node
        assert_eq!(tail, Some(44));

        let tail = *d_list.peek_back().unwrap(); // tail 现在是33
        assert_eq!(tail, 33);


        let mut tail = *d_list.peek_back_mut().unwrap();
        tail = 555;


        let mut tail = *d_list.peek_back().unwrap();  //  只是取出值， node还在

        println!("tail is {}", tail);
    }


    #[test]
    fn test_into_iter() {
        let mut d_list = DList::new();
        d_list.push_front(11);
        d_list.push_front(22);
        d_list.push_front(33);
        d_list.push_front(44);


        let mut iter = d_list.into_iter();


        let mut curr = iter.next();


        while let Some(v) = curr {
            println!("value is {}", v);

            curr = iter.next();
        }
    }


    #[test]
    fn test_into_iter2() {
        let mut d_list = DList::new();
        d_list.push_front(11);
        d_list.push_front(22);
        d_list.push_front(33);
        d_list.push_front(44);

        let mut iter = d_list.into_iter();
        let mut curr = iter.next_back();

        while let Some(v) = curr {
            println!("value is {}", v);
            curr = iter.next_back();
        }
    }
}
